package com.zp.self.module.level_4_算法练习.算法.动态规划;

/**
 * @author By ZengPeng
 */
public class 力扣_1143_最长公共子序列 {
    //测试
    public static void main(String[] args) {

//        System.out.println(new 力扣_1143_最长公共子序列().longestCommonSubsequence("a","c"));
//        System.out.println(new 力扣_1143_最长公共子序列().longestCommonSubsequence("abcde","ace"));
        System.out.println(new 力扣_1143_最长公共子序列().longestCommonSubsequence(
                "nkvmxmncnbacrcb","vcnrmxcfcxabkx"));
    }

    /**
    题目：给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
     一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
     例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
     两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

     示例 1：
     输入：text1 = "abcde", text2 = "ace"
     输出：3
     解释：最长公共子序列是 "ace" ，它的长度为 3 。

     示例 2：
     输入：text1 = "abc", text2 = "abc"
     输出：3
     解释：最长公共子序列是 "abc" ，它的长度为 3 。

     示例 3：
     输入：text1 = "abc", text2 = "def"
     输出：0
     解释：两个字符串没有公共子序列，返回 0 。

    分析：【PR 💖💖💖💖💖💖💖】
       1.动态规划：二维数组 -- 每个横纵坐标是否相等？相等则在上左 中找到最大值+1
             --执行用时：6 ms, 在所有 Java 提交中击败了92.26%的用户
             --最金典的二维数组动态规划,我也不知道怎么就写出来了，还得想想怎么解释  ( •̀ ω •́ )✧
            自我解读：每个字符串拿一部分字符出来，总共有多少种情况呢？ m * n 种
                       --> 刚好一个dp[m][n] ,记录当每个字符串 提供m个字符 ，n个字符时 能对上的个数
                        m字符串每增加一位，需要判断增加后 这个坐标的字符是否相等？ 相等时，需要判断上右是否相等，则用斜角加上+1 ，斜角0 不能直接到2
             大佬解读：
                         知道状态定义之后,我们开始写状态转移方程。
                         当 text1[i-1]=text2[j-1]时,说明两个子字符串的最后一位相等,所以最长公共子序列又増加了1,所以dp[i[j]=dp[i-1][j-1]+1;
                         举个例子,比如对于ac和bc他们的最长公共子序列的长度等于: a和b的最长公共子序列长度0+1=1
                         注意对于ac和cc他们的最长公共子序列的长度等于: a和c的最长公共子序列长度0+1=1

                         当 text1[i-1] != text2[j-1]时, 说明两个子字符串的最后一位不相等,那么此时的状态应该是dp[i][j-1]、dp[i-1][j]的最大值。
                         举个例子,比如对于ace和bc他们的最长序列的长度等于1,
                         ace和b的最长序列长度0与
                         ac和bc的最长公共子序列长度1 的最大值，即dp[i][j] = 1

                         当 text1[i-1] = text2[j-1]  , dp[i][j]=dp[i-1][j-1]+1,
                         当 text1[i-1]!= text2[j-1]  , dp[i][j]=max(dp[i-1][j],dp[i][j-1]),
    边界值 & 注意点：
       1.
     **/
    public int longestCommonSubsequence(String text1, String text2) {
        int  row = text1.length(),lie = text2.length();
        char[] char1 = text1.toCharArray();
        char[] char2 = text2.toCharArray();
        int[][] dp = new int[row][lie];
        dp[0][0] = char1[0]==char2[0]?1:0;
        for (int i = 1; i < row; i++) {//初始化第一列
            if(dp[i-1][0]==1 || char1[i] == char2[0])
                dp[i][0] =1;
        }
        for (int i = 1; i < lie; i++) {//初始化第一行
            if(dp[0][i-1]==1 || char1[0] == char2[i])
                dp[0][i] =1;
        }
        for (int x = 1; x < row; x++) {
            for (int y = 1; y < lie; y++) {
                if(char1[x]==char2[y] )
                    dp[x][y] = dp[x-1][y-1]+1;
                else
                    dp[x][y] = Math.max(dp[x-1][y],dp[x][y-1]);
            }
        }
        return  dp[row-1][lie-1];
    }
}
